#ifndef DOUBLELINKEDLIST_H
#define DOUBLELINKEDLIST_H

#include<iostream>

template <typename DT>
class List
{
	private:
		struct node
		{
			DT   data;
			node *prev;
			node *next;
			
			node(const DT & d = DT{}, node *p = nullptr,
			                          node *n = nullptr)
			    : data{d}, prev{p}, next{n}{}
			node(const DT && d, node *p = nullptr,
			                          node *n = nullptr)
			    : data{std::move(d)}, prev{p}, next{n}{}
			
		};
		
	public:
		class const_iterator
		{
			public:
				const_iterator()
					:theList{nullptr}, current{nullptr}{}
				
				const DT & operator* () const
				{
					Isemptyoruninit();	
					return retrieve();
				}
				
				const_iterator & operator++ ()
				{
					movebackIsValid();	
					current = current->next;
					return *this;
				}
				
				const_iterator operator++ (int)
				{
					movebackIsValid();	
					const_iterator old = *this;
					++( *this );
					return old;
				}
				const_iterator & operator-- ()
				{
					movefrontIsValid();	
					current = current->prev;
					return *this;
				}
				
				const_iterator operator-- (int)
				{
					movefrontIsValid();	
					const_iterator old = *this;
					--( *this );
					return old;
				}
				
				bool operator== (const const_iterator & rhs) const
				{
					return current == rhs.current;
				}
				bool operator!= (const const_iterator & rhs) const
				{
					return !(*this == rhs);
				}
				
			protected:
				const List<DT> *theList;
				node *current;
				
				const_iterator(const List<DT> & lst, node *p)
					: theList{&lst},current{p}
				{
				}
				
				void assertIsValid() const
				{
					if(theList == nullptr || current == nullptr || current == theList->head)
					{
						std::cout<<"Iterator Out of Bounds"<<std::endl;
						std::exit(-1);
						//throw IteratorOutOfBoundsExeption{};
					}
				}
				void Isemptyoruninit() const
				{
					if(current==nullptr)
					{
						std::cout<<"uninitialize"<<std::endl;
						std::exit(-1);
					}
					if(current==theList->tail)
					{
						std::cout<<"hit the tail"<<std::endl;
						std::exit(-1);
					}
					if(current==theList->head)
					{			
						std::cout<<"hit the head"<<std::endl;
						std::exit(-1);
					}
					return;
				}
				void movefrontIsValid() const
				{
					
					if(current==nullptr)
					{
						std::cout<<"uninitialize"<<std::endl;
						std::exit(-1);
					}
					if(current==theList->head)
					{
						std::cout<<"hit the head"<<std::endl;
						std::exit(-1);
					}
				}				
				void movebackIsValid() const
				{
					if(current==nullptr)
					{
						std::cout<<"uninitialize"<<std::endl;
						std::exit(-1);
					}
					if(current==theList->tail)
					{
						std::cout<<"hit the tail"<<std::endl;
						std::exit(-1);
					}
				}


				DT & retrieve() const
				{
					return current->data;
				}
				
				//const_iterator(node *p): current{p}{}
				
				friend class List<DT>;
				
		};
		
		class iterator: public const_iterator
		{
			public:
				iterator(){} 
				
				DT & operator* ()
				{
					const_iterator::Isemptyoruninit();
					return const_iterator::retrieve();
				}
				const DT & operator* () const
				{
					const_iterator::Isemptyoruninit();
					return const_iterator::operator* ();
				}
				
				iterator & operator++ ()
				{
					const_iterator::movebackIsValid();
					this->current = this->current->next;
					return *this;
				}
				
				iterator operator++ (int)
				{
					const_iterator::movebackIsValid();
					iterator old = *this;
					++(*this);
					return old;
				}
				iterator & operator-- ()
				{
					const_iterator::movefrontIsValid();
					this->current = this->current->prev;
					return *this;
				}
				
				iterator operator-- (int)
				{
					const_iterator::movefrontIsValid();
					iterator old = *this;
					--(*this);
					return old;
				}

			protected:
				iterator(const List<DT> & lst, node *p)
					: const_iterator{lst,p}{}
					
				friend class List<DT>;
				
		};
		
	public:
		List() 
		{
			init();
		}
		List(const List & rhs)
		{
			init();
			for(auto & x : rhs)
				push_back(x);
		}
		~List()
		{
			clear();
			delete head;
			delete tail;
		}
		List & operator= (const List & rhs)
		{
			List copy = rhs;
			std::swap(*this,copy);
			return *this; 
		}
		List(List && rhs)
			: theSize{rhs.theSize}, head{rhs.head}, tail{rhs.tail}
		{
			rhs.theSize = 0;
			rhs.head = nullptr;
			rhs.tail = nullptr;
		}
		List & operator= (List && rhs)
		{
			std::swap(theSize, rhs.theSize);
			std::swap(head, rhs.head);
			std::swap(tail, rhs.tail);
			
			return *this;
		}
		
		iterator begin()
		{
			return {*this,head->next};
		}
		const_iterator begin() const
		{
			return {*this,head->next};
		}
		iterator end()
		{
			return {*this,tail};
		}
		const_iterator end() const
		{
			return {*this,tail};
		}
		
		int size() const
		{
			return theSize;
		}
		bool empty() const
		{
			return size() == 0;
		}
		
		void clear()
		{
			while(!empty())
				pop_front();
		}
		
		
		DT & front()
		{
			return *begin();
		}
		const DT & front() const
		{
			return *begin();
		}
		DT & back()
		{
			return *--end();
		}
		const DT & back() const
		{
			return *--end();
		}
		void push_front(const DT & x)
		{
			insert(begin(),x);
		}
		void push_front(DT && x)
		{
			insert(begin(),std::move(x));
		}
		void push_back(const DT & x)
		{
			insert(end(),x);
		}
		void push_back(DT && x)
		{
			insert(end(),std::move(x));
		}
		void pop_front()
		{
			erase(begin());
		}
		void pop_back()
		{
			erase(--end());
		}
		// Insert x before itr.
		iterator insert(iterator itr, const DT & x)
		{
			itr.assertIsValid();
			if(itr.theList!=this)
			{
				std::cout<<"Iterator Miss Match!"<<std::endl;
				std::exit(-1);
			}
			node *p = itr.current;
			theSize++;
			return {*this, p->prev = p->prev->next 
					= new node{x,p->prev,p}};
		}
		iterator insert(iterator itr, DT && x)
		{
			itr.assertIsValid();
			if(itr.theList!=this)
			{
				std::cout<<"Iterator Miss Match!"<<std::endl;
				std::exit(-1);
			}
			node *p = itr.current;
			theSize++;
			return {*this, p->prev = p->prev->next
					= new node{std::move(x),p->prev,p}};
		}
		iterator erase(iterator itr)
		{
			itr.Isemptyoruninit();
			node *p = itr.current;
			iterator retVal{*this, p->next};
			p->prev->next = p->next;
			p->next->prev = p->prev;
			delete p;
			theSize--;
			
			return retVal;	
		}
		iterator erase(iterator from, iterator to)
		{
			from.Isemptyoruninit();
			to.Isemptyoruninit();

			for(iterator itr = from; itr != to;)
				itr = erase(itr);
				
			return to;
		}
		void printlist() const
		{
			const_iterator p = begin();
			while(p != end())
			{
				std::cout<<*p<<'\t';
				p++;
			}
			
			std::cout<<'\b'<<std::endl;
		}	
	private:
		int   theSize;
		node *head;
		node *tail;
		
		void init()
		{
			theSize = 0;
			head = new node;
			tail = new node;
			head->next = tail;
			tail->prev = head;
		}
};

template <typename DT>
typename List<DT>:: iterator find(List<DT> & lst, const DT & val)
{
	typename List<DT>::iterator p = lst.begin();
	while(p != lst.end())
	{
		if((*p)==val)
			return p;
		p++;
	}
	
	std::cout<<"No Such Element!!"<<std::endl;
	return { };
}
#endif
